package main

import (
	"fmt"
	"unicode/utf8"
)

var dp = map[string]string{}

func main() {
	var s string = "agdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65" +
		"fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd6" +
		"5fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sd" +
		"f65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdg" +
		"ggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5d" +
		"sf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sd" +
		"f65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdggg" +
		"ssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6" +
		"g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g" +
		"4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgap" +
		"ppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd" +
		"65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdf" +
		"agdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgappp" +
		"dfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4s" +
		"df65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggss" +
		"gapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd6" +
		"5fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdg" +
		"ggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6" +
		"g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfa" +
		"gdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5d" +
		"sf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65" +
		"g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapp" +
		"pdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf" +
		"65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdf" +
		"g5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4" +
		"sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5ds" +
		"f6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagd" +
		"" +
		"gggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65" +
		"fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgappp" +
		"dfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdf" +
		"agdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65" +
		"fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgappp" +
		"dfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g" +
		"4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5" +
		"dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4" +
		"sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgappp" +
		"dfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4s" +
		"65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65" +
		"fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgap" +
		"ppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgg" +
		"gssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg" +
		"5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65f" +
		"g4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggs" +
		"sgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssga" +
		"pppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf" +
		"6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g" +
		"4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg" +
		"5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfa" +
		"gdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdaaabaaafagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppd" +
		"fg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65f" +
		"" +
		"gapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdfagdgggssgapppdfg5dsf6g4sd65fg4sdf65g4sdf"

	//re := isPalindrome(s)
	//fmt.Println("re:",re)

	reStr := longestPalindrome(s)
	fmt.Println("reStr:", reStr)
}

func longestPalindrome(s string) string {
	strLen := len(s)
	if strLen <= 2 {
		return s
	}

	for i := 0; i < len(s); i++ {
		for j := len(s); j > i; j-- {

			//是否存在该回文子串
			if _, ok := dp[s[i:j]]; !ok {
				//是否符合
				if isPalindrome(s[i:j]) == true {
					dp[s[i:j]] = s[i:j]
				}
			}
		}

	}
	var reStr = ""
	max := 0
	for _, v := range dp {
		if max < utf8.RuneCountInString(v) {
			max = utf8.RuneCountInString(v)
			reStr = v
		}
	}
	return reStr
}

func isPalindrome(s string) bool {
	strLen := len(s)
	if strLen >= 2 {

		for a, b := 0, strLen-1; a < len(s)/2; {
			if s[a] != s[b] {
				return false
			}
			a++
			b--
		}
	}
	return true
}
